#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include "kmeans.h"

using namespace std;

/**********************************************************
* kmeans - constructor
* paramters:
*   -numberpoints: number of elements in dataset to cluster
*   -numberClusters: number of k-means clusters desired
************************************************************/
kmeans::kmeans(int numberPoints, int numberClusters)                                //WORKS -- TESTED 120502 CP
{
    /******initialize global variables******/
    numK = numberClusters;
    numPoints = numberPoints;
    data = new coordinates[numPoints];
    centroids = new centroid[numK];
    srand(time(NULL)); //generate seed for random # generator
    createTestData(rand());                             //creates random numbers for test of algorithm
}

/**********************************************************
* kmeans - constructor
* paramters:
*   -numberpoints: number of elements in dataset to cluster
*   -data_points: data with x,y coordiantes in 2D space
*   -numberClusters: number of k-means clusters desired
************************************************************/
kmeans::kmeans(int numberPoints, coordinates *& data_points, int numberClusters)                                //WORKS -- TESTED 120502 CP
{
    /******initialize global variables******/
    numK = numberClusters;
    numPoints = numberPoints;
    data=data_points;                       //fixed 120502 - CP
    centroids = new centroid[numK];
    srand(time(NULL)); //generate seed for random # generator
}

/*************************************************************************
* Profile -  deconstructor
*   deletes all dynamically allocated class variables
**************************************************************************/
kmeans::~kmeans()                                //WORKS -- TESTED 120502 CP
{
    delete data;
    delete centroids;
}

/************************************************************
* createTestData - generates a random dataset of coordinates
*  from the range 0 to rangeMax
* parameters
*  rangeMax - the maximum value a coordinate can contain
*************************************************************/
void kmeans::createTestData(int rangeMax)                                //WORKS -- TESTED 120502 CP
{
    for(int i = 0; i<numPoints; i++)
    {
        data[i].x = rand() % rangeMax;
        data[i].y = rand() % rangeMax;
    }

}

/**********************************************************
* print
*   prints out clusters to screen
************************************************************/
void kmeans::print()                                //WORKS -- TESTED 120502 CP
{
   for(int j = 0; j < numK; j++)
    {
        cout << "Centroid: " << centroids[j].x << ", " << centroids[j].y << "\t" << centroids[j].prob << endl;
    }
}

/************************************************************
* pickCentroids - assigns random coordinates from datasetř23
*  as initial centroids
* parameters:
*   -picked: array that keeps track of which data points
*   have already been chosen as centroids
*************************************************************/
void kmeans::pickCentroids(bool *& picked)                                //WORKS -- TESTED 120502 CP
{
    for(int i=0; i<numPoints; i++) //no data point selected as centroid yet so set everything to false
    {
        picked[i] = false;

    }

    for(int j=0; j<numK; j++)
    {
        int random = rand() % numPoints;
        cout << "numPoints " << numPoints << endl;
        if(picked[random]!= true)       //assign random datapoint as centroid
        {
            centroids[j].x = data[random].x;
            centroids[j].y = data[random].y;
            picked[random]=true;
            cout << "picked something, so j goes up?" << endl;
        }
        else
        {
            j--; //pick another data point
        }
        cout << "j: " << j << " numK: " << numK << endl;
    }
}//end pickCentroids

/*******************************************************************
* initializeCluster - assigns data points to a cluster
*  using the euclidean distance metric
* parameters:
*   -labels: keeps track of which cluster each data point belongs to
********************************************************************/
void kmeans::initializeCluster(int *& labels)                                //WORKS -- TESTED 120502 CP
{
    for(int i=0; i<numPoints; i++)
    {
        int min_cluster = 0; //cluster that contains the centroid that is closest distance from specified data point
        float min_distance = sqrt(pow(centroids[0].x - data[i].x, 2) + pow(centroids[0].y - data[i].y, 2)); //calculate euclidean distance
        for(int j=1; j<numK; j++)   //calculate distance between a data point and each centroid
        {
            float curr_distance = sqrt(pow(centroids[j].x - data[i].x, 2) + pow(centroids[j].y - data[i].y, 2));
            if(curr_distance < min_distance)
            {
                min_distance=curr_distance;
                min_cluster=j;
            }
        }
        labels[i] = min_cluster;
    }
}//end initializeCluster

/*****************************************************************
* calculateCentroids - calculates new centroids based on averaging
*  the data points within a cluster
* parameters:
*   -labels: keeps track of which cluster each data point belongs to
*   -picked: array that keeps track of which data points have already
*    been chosen as centroids
*   -tempCentroids: holds the new centroid until the error function
*    is calculated
*******************************************************************/
bool kmeans::calculateCentroids(int labels[], bool *& picked, coordinates *& tempCentroids)                                //WORKS -- TESTED 120502 CP
{
    for(int i = 0; i < numK; i++)
    {
        long long clusterSize = 0;
        float sumX = 0; //sum of all the x-coordinates in a cluster
        float sumY = 0; //sum of all the y-coordinates in a cluster

        for(int j = 0; j < numPoints; j++)
        {
            if(labels[j]==i) //if data point belongs to cluster i
            {
                sumX+=data[j].x;
                sumY+=data[j].y;
                clusterSize++;
            }
        }

        centroids[i].prob=(float)clusterSize/(float)numPoints;                          //updated 120502 - CP

        if(clusterSize == 0)  //there are no data points in the cluster
        {
            srand(time(NULL));
            int random = rand() % numPoints;
            if(picked[random] == false) //pick new centroid
            {
                centroids[i].x = data[random].x;
                centroids[i].y = data[random].y;
                picked[random] = true;
            }
            return true; //continues the loop to reinitialize clusters
        }
        else //calculate new centroids
        {
            tempCentroids[i].x = sumX/(float)clusterSize;
            tempCentroids[i].y = sumY/(float)clusterSize;
        }
    }//end for loop
    return false;
}//end calculateCentroids


/*****************************************************************
* updateCentroids - calculates new centroids based on values
*  generated by an objective function
* parameters:
*   -labels: keeps track of which cluster each data point belongs to
*   -tempCentroids: holds the new centroid until the error function
*    is calculated
*******************************************************************/
bool kmeans::updateCentroids(int labels[], coordinates tempCentroids[])                                //WORKS -- TESTED 120502 CP
{
    float centroidError = 0; //initial centroid error value
    float tempCentroidError = 0;  //recalculated centroid error value
    for(int i=0; i<numPoints; i++) //calculate error values from objective function
    {
        centroidError += pow(centroids[labels[i]].x-data[i].x, 2) + pow(centroids[labels[i]].y-data[i].y, 2);
        tempCentroidError += pow(tempCentroids[labels[i]].x-data[i].x, 2) + pow(tempCentroids[labels[i]].y-data[i].y, 2);
    }

    if(centroidError <= tempCentroidError) //optimal centroids found
    {
        return false; //finish loop
    }
    else //optimal centroids not found
    {
        //move the centroids
        for(int j = 0; j<numK; j++)
        {
            centroids[j].x = tempCentroids[j].x;
            centroids[j].y = tempCentroids[j].y;
        }
        return true; //continue looping to find optimal centroids
    }
}

/*****************************************************************
* execute - runs the k-means clustering upon call to function
* parameter:
*       -c: centroids returned for data
*******************************************************************/
void kmeans::execute(centroid *& c)                                //WORKS -- TESTED 120502 CP
{
    bool * pickedPts = new bool[numPoints]; //holds information on whether a datapoint is being used as a centroid
    coordinates * temp = new coordinates[numK]; //holds temporary centroids
    int * labels = new int[numPoints]; //holds information on which cluster each data point belongs to
    bool overall_loop = true;
    bool calc_loop = false;

    for(int i=0; i<numPoints; i++)
    {
        pickedPts[i] = false;
    }

    //createTestData(50); //generate test dataset
    pickCentroids(pickedPts);
    while(overall_loop == true) //move centroids until the optimal is found
    {
        initializeCluster(labels);
        calc_loop = calculateCentroids(labels, pickedPts, temp);
        if(calc_loop == true) //if new clusters need to be calculated skip updateCentroids()
        {
          continue;
        }
        overall_loop = updateCentroids(labels, temp);
    }
    c=centroids;

    //clean up memory
    delete pickedPts;
    delete temp;
    delete labels;
}
